package DataStructure.tree;

import DataStructure.linear.Queue;

public class PagerFolding {
    public static void main(String[] args) {
        //模拟折纸过程。产生树
        Node<String> tree = createTree(2);
        //遍历树打印节点
        printTree(tree);
    }

    //产生树,使用前序遍历
    public static Node<String> createTree(int N){
        //根节点
        Node<String> root=null;
        for (int i = 0; i < N; i++) {
            //1.当前第一次对折
            if(i==0){
                root=new Node<>("down",null,null);
                continue;
            }
            //2.不是第一次对折
            //定义一个辅助队列，
            Queue<Node> queue = new Queue<>();
            queue.enqueue(root);
            while (!queue.isEmpty()){
                //弹出一个结点
                Node<String> tmp = queue.dequeue();
                //如果有左子节点，则把左子节点放入队列中
                if(tmp.left!=null){
                    queue.enqueue(tmp.left);
                }
                //如果有右子节点，则把右子节点放入队列中
                if(tmp.left!=null){
                    queue.enqueue(tmp.right);
                }
                //如果都没有，证明给节点是叶子节点只需给该节点添加左右节点即可
                if(tmp.left==null && tmp.right==null){
                    tmp.left=new Node<String>("down",null,null);
                    tmp.right=new Node<String>("up",null,null);
                }

            }
        }
        return root;
    }







    //打印每个节点
    public static  void printTree(Node<String> root){
        if(root==null){
            return;
        }
        //使用中序遍历
        //打印左子树每个节点
        if(root.left!=null){
            printTree(root.left);
        }
        //打印当前节点
        System.out.print(root.item+"  ");
        //打印右子树每个节点
        if(root.right!=null){
            printTree(root.right);
        }

    }


    //节点类
    private static class Node<T>{
        public T item;
        public Node left;
        public Node right;
        public  Node(T item,Node left,Node right){
            this.item=item;
            this.left=left;
            this.right=right;
        }
    }



}
